# 1 两数之和
# leetcode第1题: https://leetcode.cn/problems/two-sum/
# Date: 2024/10/15

def twoSum(nums: list[int], target: int) -> list[int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]


def twoSum_hashtable(nums: list[int], target: int) -> list[int]:
    """
    使用哈西表算法可以显著降低时间复杂度, 从暴力算法的O(n^2) -> O(n)
    """
    hashtable = dict()  # 创建一个字典格式为 num:index
    for i, num in enumerate(nums):
        if target - num in hashtable:  # 如果在字典中存在符合条件的num则返回对应的索引
            return [hashtable[target - num], i]
        hashtable[nums[i]] = i  # 如果不存在则在字典中添加这个映射
    return []


if __name__ == '__main__':
    nums = [3, 3]
    target = 6
    result = twoSum(nums, target)
    print(f'case 1: {result}')
    nums = [2, 7, 11, 15]
    target = 9
    result = twoSum_hashtable(nums, target)
    print(f'case 2: {result}')
    nums = [3, 2, 4]
    target = 6
    result = twoSum_hashtable(nums, target)
    print(f'case 3: {result}')
